/*
 * Add Two Numbers
You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
 */
package com.xinpan.exercise;


public class AddTwoNumber {
		    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
		        // Start typing your Java solution below
		        // DO NOT write main() function
		        int cur = (l1.val + l2.val) % 10;
		        int forward = (l1.val + l2.val) / 10;
		        ListNode newNode = new ListNode(cur);
		        ListNode head = newNode;
		        
		        for(l1 = l1.next, l2 = l2.next; l1 != null && l2 != null; l1 = l1.next, l2 = l2.next)
		        {
		            int val = l1.val + l2.val + forward;
		            ListNode curNode = new ListNode(val % 10);
		            newNode.next = curNode;
		            newNode = curNode;
		            
		            forward = val / 10;
		        }
		        
		        if(l1 == null && l2 == null)
		        {
		            if(forward != 0)
		            {
		                ListNode curNode = new ListNode(forward);
		                newNode.next = curNode;
		            }
		            return head;
		        }
		        else if(l2 != null)
		            l1 = l2;
		            
		        for(; l1 != null; l1 = l1.next)
		        {
		            int val = l1.val + forward;
		            ListNode curNode = new ListNode(val % 10);
		            newNode.next = curNode;
		            newNode = curNode;
		            
		            forward = val / 10;
		        }
		        
		        if(forward != 0)
		            newNode.next = new ListNode(forward);
		            
		        return head;
		    }

}

		
class ListNode {
	int val;
	ListNode next;
	
	public ListNode(int x) 
	{
		val = x;
		next = null;
	}
}
			 
